Từ nhỏ vì tránh kẻ thù, ngụ cư ở Giang Hạ. Cuối thời nhà Tân, gia nhập nghĩa quân Lục Lâm. Canh Thủy đế lên ngôi, Vũ được nhiệm chức Thị lang, cùng Lưu Tú đại phá bọn Vương Tầm. Được bái làm Chấn uy tướng quân, cùng Thượng thư lệnh Tạ Cung đi đánh Vương Lang.

Về sau Lưu Tú hạ được Hàm Đan, mời Cung và Vũ đến dự tiệc, muốn tìm cơ hội giết chết Cung, nhưng không thành công. Lưu Tú mời riêng Vũ lên Tùng đài mà thuyết hàng, ông tỏ ý bằng lòng. Sau khi Cung bị giết, Vũ cưỡi ngựa đến Xạ Khuyển đầu hàng Lưu Tú. Ông ta rất hài lòng, cắt đặt ở bên cạnh. Mỗi khi Lưu Tú úy lạo chư tướng, Vũ đều giúp ông ta rót rượu, Lưu Tú rất vui.

Lưu Tú sai ông đem quân bản bộ đến Nghiệp, Vũ dập đầu từ chối, Lưu Tú càng hài lòng về ông, cho theo đại quân chinh chiến. Lưu Tú đánh quân nông dân Vưu Lai, Ngũ Phiên, thua ở Thận Thủy, chỉ còn mỗi Vũ ở phía sau, vẫn gắng sức chiến đấu, khiến kẻ địch không dám truy kích. Sau đó đánh An Thứ, Tiểu Quảng Dương, Vũ thường làm tiên phong, ra sức chiến đấu, các tướng đưa quân đi theo mà phá được giặc. Ông đuổi đến Bình Cốc, Tuấn Mỹ rồi về.

Lưu Tú lên ngôi, Vũ được nhiệm chức Thị trung, Kỵ đô úy, Sơn Đô hầu. Năm Kiến Vũ thứ 4 (28), Vũ cùng bọn Hổ nha đại tướng quân Cái Duyên chinh thảo Lưu Vĩnh, ông soái quân đánh Tế Âm [2], hạ Thành Vũ, Sở Khâu, nhờ công được bái làm Bộ lỗ tướng quân.

Năm sau (29), Bàng Manh chống lại Lưu Tú, Vũ soái quân tấn công Đào Thành, đánh lui quân địch. Lưu Tú đưa đại quân đến, Manh thua chạy.

Năm thứ 6 (30), Vũ cùng Kiến uy đại tướng quân Cảnh Yểm đánh Ngôi Hiêu, chiến sự bất lợi, quân Hán rút lui. Ngôi Hiêu đuổi theo, ông tuyển tinh kỵ đi sau, tự mặc giáp cầm kích, giết hơn ngàn quân địch, Hiêu đành lui về, các cánh quân Hán đều được an toàn.